package TriePackage;



/**
 * @author Lzm
 * @version 1.0
 */
public class Trie {

  // 前缀树的根节点
  private TrieNode root;

  // 前缀树的树节点
  public class TrieNode{
    private int pass;
    private int end;
    private TrieNode[] nexts;

    // TrieNode的初始化
    public TrieNode(){
      pass = 0;
      end = 0 ;
      nexts = new TrieNode[26];
    }
  }
  // Trie的初始化
  public Trie(){
    this.root = new TrieNode();
  }

  // 前缀树的插入字符串方法
  public void insert(String word){
    if (word == null || word.length() == 0 || "".equals(word)){
      return;
    }
    // 假设word = "abc";
    // 1. 添加字符串都是先从root节点开始
    TrieNode node = root;
    node.pass++;
    for (int i = 0 , path ; i < word.length() ; i++){
      // 2. 找到node对应的next节点
      path = word.charAt(i) - 'a';
      // 3. 如果next节点为空, 则新建一个节点
      if (node.nexts[path] == null){
        node.nexts[path] = new TrieNode();
      }
      // 4. 若next节点不为空, 则令node为next节点
        node.nexts[path].pass++;
        node = node.nexts[path];
    }
    // 5. word字符串遍历结束后, 将最后一个节点end++;
    node.end++;
  }

  // 前缀树的搜索方法
  // 返回字符串word在前缀树中出现的次数
  public int searchCount(String word){
    if (word == null || word.length() == 0 || "".equals(word)){
      return 0;
    }
    TrieNode node = root;
    for (int i = 0 , path; i < word.length() ; i++){
      path = word.charAt(i) - 'a';
      if (node.nexts[path] == null){
        return 0;
      }
      node = node.nexts[path];
    }
    return node.end;
  }

  // 返回以字符串word开头的字符串在前缀树中出现的次数
  public int startWithCount(String word){
    if (word == null || word.length() == 0 || "".equals(word)){
      return 0;
    }
    TrieNode node = root;
    for (int i = 0 , path ; i < word.length() ; i++){
      path = word.charAt(i) - 'a';
      if (node.nexts[path] == null){
        return 0;
      }
      node = node.nexts[path];
    }
    return node.pass;
  }


  // 删除字符串word一次
  public void delete(String word){
    if (word == null || word.length() == 0 || "".equals(word)){
      return;
    }
    // 如果word没有在前缀树中出现则直接返回
    if (searchCount(word) <= 0){
      return;
    }

    TrieNode node = root;
    node.pass--;

    for (int i = 0 , path ; i < word.length() ; i++){
      path = word.charAt(i) - 'a';
      // 如果节点pass减1后为0, 说明此节点链断了, 也是返回
      if (--node.nexts[path].pass == 0){
        node.nexts[path] = null;
        return ;
      }
      node = node.nexts[path];
    }
    node.end--;
  }
}
